Abstract: Graphs are structures formed by a set of vertices also called nodes and set of edges that are connections between pairs of vertices. Graph clustering is the task of grouping the vertices of the graph into clusters taking into consideration the edge structure of the graph in such a way that there should be many edges within each cluster and relatively few between the clusters. Here we present a polynomial time algorithm clustering a given graph according to modified BFS algorithm.

Keywords: Clustering, Vertices, nodes, BFS.